﻿
/*
用数组实现字典树
*/
#include <iostream>
#include<string>
using namespace std;
const int N = 26;		//对应26个英文字母
const int M = 105;		//输入单词最长长度

int trie[M][N] = { 0 };		//节点数组
int cnt[M] = { 0 };			//统计该节点有多少个单词
int idx = 0;			//标识

void insert(string s)		//插入函数
{
	int p = 0;		//p=0代表进入了根节点
	for (int i = 0; i < s.length(); i++) {
		int c = s[i] - 'a';
		if (!trie[p][c]) trie[p][c] = ++idx;		//如果节点为空，加入数字
		p = trie[p][c];			//p移到数组的下一行
	}
	cnt[p]++;		//以该字母为结束的单词数加一
}
int query(string s)		//查询函数
{
	int p = 0;		//从根节点进入
	for (int i = 0; i < s.length(); i++) {
		int c = s[i] - 'a';
		if (!trie[p][c])return 0;		//如果该节点为空，返回0
		p = trie[p][c];		//如果该节点不为空，则向下移
	}
	return cnt[p];		//返回标识
}
int main()
{
	int in = 10;
	string s;
	while (in) {
		cout << "请输入数字进行操作：1.插入；2.查询；3.退出" << endl;
		cin >> in;
		switch (in)
		{
		case 1: {
			cout << "请输入：" << endl;
			cin >> s;
			insert(s);
			cout << s << "插入成功" << endl;
			break; }
		case 2: {
			cout << "请输入：" << endl;
			cin >> s;
			if (query(s))
				cout << s << "在字典树中查询到" << endl;
			else
				cout << s << "未查找到" << endl;
			break;
		}
		case 3: {
			return 0;
		}
		default: {
			cout << "输入错误！请重新输入" << endl;
		}
				 break;
		}
	}
	return 0;
}